GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>K-partiter Graph</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><i>k</i>-partiter Graph</h1>

</header>

</div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-partiter Graph</b> ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein <a href="Einfacher_Graph" title="Einfacher Graph">einfacher Graph</a>, dessen Knotenmenge in <i>k</i> disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=2}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bd301789e1f25a3da4be297ff637754ebee5f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=2}" loading="lazy"></span> heißen diese Graphen <a href="Bipartiter_Graph" title="Bipartiter Graph">bipartite Graphen</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

<p>Eine <i><b>k</b></i>-<b>Partition</b> eines Graphen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"></span> ist eine Zerlegung der Knotenmenge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> disjunkte Teilmengen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1},\ldots ,V_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{1},\ldots ,V_{k}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/08df55f60b76571ee39c5acbce164629e9c9be38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.032ex; height:2.509ex;" alt="{\displaystyle V_{1},\ldots ,V_{k}}" loading="lazy"></span>, sodass keine <a href="Nachbarschaft_(Graphentheorie)" title="Nachbarschaft (Graphentheorie)">adjazenten</a> Knoten in der gleichen Menge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f300b83673e961a9d48f3862216b167f94e5668c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.155ex; height:2.509ex;" alt="{\displaystyle V_{i}}" loading="lazy"></span> liegen, das heißt

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{i}\rightarrow \{v,w\}\not \in E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ef1d9b0a21d6037f9be97e262e0cf19332487dd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:46.496ex; height:2.843ex;" alt="{\displaystyle \forall i\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{i}\rightarrow \{v,w\}\not \in E}" loading="lazy"></span>.</dd></dl>

<p>Man beachte, dass eine solche <i>k</i>-Partition nicht eindeutig ist. Es ist durchaus möglich, dass es mehrere <i>k</i>-Partitionen gibt, die diese Eigenschaft erfüllen. Ein Graph heißt nun <i><b>k</b></i>-<b>partit</b>, falls er eine <i>k</i>-Partition besitzt. Man nennt den Graphen <b>vollständig k-partit</b>, falls außerdem jeder Knoten mit allen Knoten aller anderen <i>k</i>-Partitionen verbunden ist, wenn also gilt:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i\neq j\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{j}\rightarrow \{v,w\}\in E}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a7086c294497048ffa77b575e2c6f86d5cc23335.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:50.663ex; height:3.009ex;" alt="{\displaystyle \forall i\neq j\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{j}\rightarrow \{v,w\}\in E}" loading="lazy"></span>.</dd></dl>

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{n_{1},\ldots ,n_{k}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7126d79e0a35377fbb0a88a6637c98d4524ab9dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.709ex; height:2.843ex;" alt="{\displaystyle K_{n_{1},\ldots ,n_{k}}}" loading="lazy"></span> notiert man einen vollständig <i>k</i>-partiten Graphen, mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V_{i}|=n_{i}}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V_{i}|=n_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c6ddfea59ec9518965f27176c4e820c313ac31ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.741ex; height:2.843ex;" alt="{\displaystyle |V_{i}|=n_{i}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel_Turán-Graph"><span id="Beispiel_Tur.C3.A1n-Graph"></span>Beispiel Turán-Graph</h2></div>

<p>Die <a href="Satz_von_Tur%C3%A1n" title="Satz von Turán">Turán-Graphen</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{m}(n)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{m}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7503a20e2773b8f73c2058f19305a661aae245e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.237ex; height:2.843ex;" alt="{\displaystyle T_{m}(n)}" loading="lazy"></span> (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3\leq m<n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3\leq m<n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/305e7df91c11f5c62e6a10fc60de234b175dd877.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.794ex; height:2.343ex;" alt="{\displaystyle 3\leq m<n}" loading="lazy"></span>) sind vollständige <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span>-partite Graphen. Das nebenstehende Beispiel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{3}(7)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{3}(7)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a4536c7e5b2731bee0f00cb383323bcf1f8886fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.384ex; height:2.843ex;" alt="{\displaystyle T_{3}(7)}" loading="lazy"></span> ist 3-partit. Bezeichnet <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor \cdot \rfloor }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor \cdot \rfloor }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ddb5178c0fbe4ac275f1083ee8f1a6e0feb8f872.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.712ex; height:2.843ex;" alt="{\displaystyle \lfloor \cdot \rfloor }" loading="lazy"></span> die <a href="Floor-Funktion" class="mw-redirect" title="Floor-Funktion">Floor-Funktion</a>, so ist

</p>

<msub>

</mrow>

</msub>

<msub>

<mfrac>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{m}(n)=K_{\lfloor {\frac {n}{m}}\rfloor ,\lfloor {\frac {n+1}{m}}\rfloor ,\ldots ,\lfloor {\frac {n+m-1}{m}}\rfloor }}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b2a98895d7019cf6105fcebd3867f1cf6fcf7af8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:30.119ex; height:4.009ex;" alt="{\displaystyle T_{m}(n)=K_{\lfloor {\frac {n}{m}}\rfloor ,\lfloor {\frac {n+1}{m}}\rfloor ,\ldots ,\lfloor {\frac {n+m-1}{m}}\rfloor }}" loading="lazy"></span>.</dd></dl>

<p>Für das nebenstehende Beispiel gilt damit

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{3}(7)=K_{2,2,3}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2d556f028eef71e239f8b2b150033b05dc342e41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.068ex; height:3.009ex;" alt="{\displaystyle T_{3}(7)=K_{2,2,3}}" loading="lazy"></span>.</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

<ul><li>Jeder k-partite Graph ist <a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">k-knotenfärbbar</a>. Dabei wird jeder Partitionsklasse eine Farbe zugewiesen. Die Frage, ob ein Graph k-partit ist, ist also äquivalent zu der Frage, ob der Graph k-knotenfärbbar ist. Die <a href="Chromatische_Zahl" title="Chromatische Zahl">chromatische Zahl</a> eines Graphen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> ist somit das kleinste <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>, sodass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> eine <i>k</i>-Partition besitzt.</li>

<li>Jeder <i>k</i>-partite Graph ist auch immer ein <i>k</i>+<i>x</i>-partiter Graph, wobei <i>x</i> eine natürliche Zahl und <i>k</i>+<i>x</i> kleiner als die <a href="Knotenzahl" title="Knotenzahl">Knotenzahl</a> ist.</li>

<li>Ein vollständig <i>k</i>-partiter Graph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{n_{1},\ldots ,n_{k}}}">

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{n_{1},\ldots ,n_{k}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7126d79e0a35377fbb0a88a6637c98d4524ab9dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.709ex; height:2.843ex;" alt="{\displaystyle K_{n_{1},\ldots ,n_{k}}}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{1}\leq \ldots \leq n_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{1}\leq \ldots \leq n_{k}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e05c82976ac4dcf6223e8e882d986308d1290453.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.853ex; height:2.343ex;" alt="{\displaystyle n_{1}\leq \ldots \leq n_{k}}" loading="lazy"></span> besitzt immer ein <a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">Matching</a> der Größe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \min\{\sum _{i=1}^{k-1}n_{i},\lfloor {\frac {1}{2}}\sum _{i=1}^{k}n_{i}\rfloor \}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min\{\sum _{i=1}^{k-1}n_{i},\lfloor {\frac {1}{2}}\sum _{i=1}^{k}n_{i}\rfloor \}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a409207114ca76d2ae38ca1b01cb1bfe561348e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:23.558ex; height:7.343ex;" alt="{\displaystyle \min\{\sum _{i=1}^{k-1}n_{i},\lfloor {\frac {1}{2}}\sum _{i=1}^{k}n_{i}\rfloor \}}" loading="lazy"></span>, welches <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">effizient</a> berechnet werden kann.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Reinhard_Diestel" title="Reinhard Diestel">Reinhard Diestel</a>: <cite style="font-style:italic">Graphentheorie</cite>. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (<a rel="nofollow" class="external text" href="https://diestel-graph-theory.com/">diestel-graph-theory.com</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-partiter+Graph&rft.au=Reinhard+Diestel&rft.btitle=Graphentheorie&rft.date=2010&rft.edition=4.&rft.genre=book&rft.isbn=9783642149115&rft.place=Berlin&rft.pub=Springer" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li>Eric W. Weisstein: <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/k-PartiteGraph.html"><i>k-Partite Graph</i>.</a> In: <i><a href="MathWorld" title="MathWorld">MathWorld</a></i> (englisch).</li>

<li>Eric W. Weisstein: <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/Completek-PartiteGraph.html"><i>Complete k-Partite Graph</i>.</a> In: <i><a href="MathWorld" title="MathWorld">MathWorld</a></i> (englisch).</li>

<li>Boris Bukh, Kevin Ferguson: <a rel="nofollow" class="external text" href="https://planetmath.org/KPartiteGraph"><i>k-partite graph</i>.</a> In: <i><a href="PlanetMath" title="PlanetMath">PlanetMath</a>.</i> (englisch)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">D. Sitton: <i>Maximum Matchings in complete multipartite Graphs.</i> In: <i>Electronic Journal of Undergraduate Mathematics.</i> Volume 00, 1996, S. 6–16.</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2023-12-11" href="https://de.wikipedia.org/wiki/?title=K-partiter_Graph&oldid=240098360">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>